package com.yxyu.sort.impl;

import com.yxyu.sort.SortBase;

/**
 * 归并排序
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
 *
 */
public class MergeSort implements SortBase {

    @Override
    public String getName() {
        return "归并排序";
    }

    @Override
    public int[] sort(int[] numbers) {
        return sortMerge(numbers, 0, numbers.length - 1);
    }

    private int[] sortMerge(int[] numbers, int begin, int end) {
        if (end == begin) {
            // 出口
            return numbers;
        }

        int m = (begin + end) / 2;
        sortMerge(numbers, m + 1, end);
        sortMerge(numbers, begin, m);
        sort(numbers, begin, m, end);
        return numbers;
    }

    private void sort(int[] a, int left, int mid, int right) {
        // 中间数组
        int[] tmp = new int[right - left + 1];
        int p1 = left, p2 = mid + 1, k = 0;

        // 对比填充
        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2])
                tmp[k++] = a[p1++];
            else
                tmp[k++] = a[p2++];
        }

        // 空余填充
        while (p1 <= mid) tmp[k++] = a[p1++];
        while (p2 <= right) tmp[k++] = a[p2++];

        // 复制回原素组
        for (int i = left; i <= right; i++)
            a[i] = tmp[i - left];
    }
}
